#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 30
#define INFINITY 9999
typedef int element_type;
typedef struct Arc
{
    int tail, head;
    int weight;
    struct Arc *in, *out;
};
typedef struct Node
{
    element_type data;
    struct Arc *fristin, *fristout;
};

typedef struct Orth_list
{
    Node box[MAXSIZE];
    int nodenum, arcnum;
};

Orth_list transform_orth_list(int a[MAXSIZE][MAXSIZE], int node[], int nodenum)
{
    Orth_list G;
    G.nodenum = nodenum;
    for (int i = 0; i < nodenum; i++)
    {
        G.box[i].data = node[i];
        G.box[i].fristin = G.box[i].fristout = NULL;
    }
    //CREAT outdegree
    for (int k = 0; k < nodenum; k++)
    {
        for (int j = nodenum - 1; j >= 0; j--)
        {
            if (a[k][j] != 0 && a[k][j] != INFINITY)
            {
                Arc *arctemp = (Arc *)malloc(sizeof(Arc));
                arctemp->head = k;
                arctemp->tail = j;
                arctemp->weight = a[k][j];
                arctemp->in = arctemp->out = NULL;
                arctemp->out = G.box[k].fristout;
                G.box[k].fristout = arctemp;
            }
        }
    }
    for (int k = 0; k < nodenum; k++)
    {
        for (int j = nodenum - 1; j >= 0; j--)
        {
            if (a[j][k] != 0 && a[j][k] != INFINITY)
            {
                //SREACH BOX[J]
                Arc *temp = G.box[j].fristout;
                while (temp && temp->tail != k)
                {
                    temp = temp->out;
                }
                temp->in = G.box[k].fristin;
                G.box[k].fristin = temp;
            }
        }
    }
    return G;
}
void vist_out(Orth_list G)
{
    printf("vist_out:\n");

    for (int i = 0; i < G.nodenum; i++)
    {
        printf("%2d", G.box[i].data);
        Arc *t = G.box[i].fristout;
        while (t)
        {
            printf("---> <%d,%d> [%2d]", t->head, t->tail, t->weight);
            t = t->out;
        }
        printf("\n");
    }
}
void vist_in(Orth_list G)
{
    printf("vist_in:\n");

    for (int i = 0; i < G.nodenum; i++)
    {
        printf("%2d", G.box[i].data);
        Arc *t = G.box[i].fristin;
        while (t)
        {
            printf("---><%d,%d>[%d]", t->head, t->tail, t->weight);
            t = t->in;
        }
        printf("\n");
    }
}
int main()
{
    /*******************code*******************/
    int data2[] = {0, 1, 2, 3, 4, 5, 6};
    int weight_matrix[30][30] = {{INFINITY, 2, INFINITY, 1, INFINITY, INFINITY, INFINITY},
                                 {INFINITY, INFINITY, INFINITY, 3, 10, INFINITY, INFINITY},
                                 {4, INFINITY, INFINITY, INFINITY, INFINITY, 5, INFINITY},
                                 {INFINITY, INFINITY, 2, INFINITY, 2, 8, 4},
                                 {INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, 6},
                                 {INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY},
                                 {INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, 1, INFINITY}};

    Orth_list G = transform_orth_list(weight_matrix, data2, 7);
    vist_out(G);
    vist_in(G);
    /******************************************/
    printf("\n\n****************************\n");
    printf("Press Enter key to continue\n");
    getchar();
    return 0;
    /******************************************/
}
